package com.jc.projecteuler.january;

import java.util.*;

/**
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * <p>
 * What is the largest prime factor of the number 600851475143 ?
 */
public class Problem3 {

    public static void main(String[] args) {


        long num = 600851475143l;
//        long num = 100000000;
        long max = 0;
        long beginTime = System.currentTimeMillis();
        max = getLargestPrimeFactor(num);
        System.out.println("largest prime factor is " + max + ", cost " + (System.currentTimeMillis() - beginTime) + "ms");


    }/**output:
      *largest prime factor is 6857, cost 1ms
     */


    /**
     * 答案：
     * 假设给定一个数num, 和给定一个factor=2,3,4,5...。对于每个k，如果k是num的一个因数，则num除于k，直到除尽位置，k才往下累加到下一个k
     * <p>
     * 很容易看出，当k是一个因数时，它也是个质数，当所有小的因数被除去后，那么当num=1时，则此因数就是最大的质因数
     *
     * @param num
     * @return
     */
    private static long getLargestPrimeFactor(long num) {
        long max = 0;
        for (long factor = 2; num > 1; factor++) {
            if (num % factor == 0) {
                max = factor;
                while (num % factor == 0) {
                    num /= factor;
                }
            }
        }
        return max;
    }

    /**
     * 太慢了，根本求不出
     *
     * @param num
     * @return
     */
    @Deprecated
    private static long getMaxPrimeFactor(long num) {
        long max = 0;
        for (long i = 2; i <= num; i++) {
            if (num % i == 0) { // 判断是否是因子(factor)
                //再继续判断是否是质因子(prime factor)
                boolean isPrimeFactor = true;
                for (long j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        isPrimeFactor = false;
                        break;
                    }
                }

                if (isPrimeFactor) {
                    if (i > max)
                        max = i;
                }


            }
        }
        return max;
    }


    /**
     * 太慢了，根本求不出
     *
     * @param num
     * @return
     */
    @Deprecated
    private static long getMaxPrimeFactor2(long num) {
        List<Long> primes = new LinkedList<>();
        for (long p = 2; p <= num; p++) {
            if (isPrimeFactor(p))
                primes.add(p);
        }
        System.out.println("cache all prime finish!");

        long max = 0;
        for (long i = 2; i <= num; i++) {
            if (num % i == 0) {

                Iterator<Long> it = primes.iterator();
                while (it.hasNext()) {
                    long prime = it.next();
                    if (prime == i) {
                        it.remove();
                        if (prime > max) {// 判断是否是因子(factor)
                            max = prime;
                            break;
                        }
                    }

                }


            }
        }
        return max;
    }

    @Deprecated
    private static boolean isPrimeFactor(long p) {
        boolean isPrimeFactor = true;
        //判断p是否是质数
        for (long j = 2; j <= Math.sqrt(p); j++) {
            if (p % j == 0) {
                isPrimeFactor = false;
                break;
            }
        }
        return isPrimeFactor;
    }


    /**
     * 太慢了，根本求不出
     *
     * @param num
     * @return
     */
    @Deprecated
    private static long getMaxPrimeFactor2Hash(long num) {
        Object o = new Object();
        Map<Long, Object> primes = new HashMap<>();
        for (long p = 2; p <= num; p++) {
            if (isPrimeFactor(p))
                primes.put(p, o);
        }


        long max = 0;
        for (long i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                Object test = primes.get(i);// 判断是否是因子(factor)
                if (test != null) {
                    if (i > max) {
                        max = i;
                        break;
                    }

                }


            }
        }
        return max;
    }


}

